package com.gaogzhen.datastructure.graph.directed;

import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.Queue;

import java.util.Iterator;

/**
 *  有向图可达性
 */
public class DirectedDFS {
    /**
     * 标记
     */
    private boolean[] marked;

    /**
     * 可达顶点计数
     */
    private int count;

    /**
     * 计算从起点s可达的顶点
     * @param G 有向图
     * @param s 起点
     * @throws IllegalArgumentException unless {@code 0 <= s < V}
     */
    public DirectedDFS(Digraph G, int s) {
        marked = new boolean[G.V()];
        validateVertex(s);
        bfs(G, s);
    }

    /**
     * 计算从sources所有顶点可达的所有顶点
     * @param G 有向图
     * @param sources 多个起点
     * @throws IllegalArgumentException if {@code sources} is {@code null}
     * @throws IllegalArgumentException unless {@code 0 <= s < V}
     *         for each vertex {@code s} in {@code sources}
     */
    public DirectedDFS(Digraph G, Iterable<Integer> sources) {
        marked = new boolean[G.V()];
        validateVertices(sources);
        for (int v : sources) {
            if (!marked[v]) {
                bfs(G, v);
            }
        }
    }

    /**
     * 广度优先搜索从地点s可达的所有顶点
     * @param G 无向图
     * @param s 起点
     */
    private void bfs(Digraph G, int s) {
        Queue<Integer> q = new Queue<Integer>();
        marked[s] = true;
        count++;
        q.enqueue(s);
        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    marked[w] = true;
                    count++;
                    q.enqueue(w);
                }
            }
        }
    }

    /**
     * 深度优先计算从起点s可达的所有顶点
     * @param digraph   有向图
     * @param s 起点
     */
    private void dfs(Digraph digraph, int s) {
        // 栈记录搜索路径
        Stack<Iterator<Integer>> path = new Stack<>();
        if (!marked[s]) {
            // 起点未标记，标记计数加1
            // 起点默认没标记，可以不加是否标记判断
            marked[s] = true;
            count++;
            Iterable<Integer> iterable = digraph.adj(s);
            Iterator<Integer> it;
            if (iterable != null && (it = iterable.iterator()) != null){
                // 顶点对应的邻接表迭代器存入栈
                path.push(it);
            }
        }
        while (!path.isEmpty()) {
            Iterator<Integer> it = path.pop();
            int x;
            while (it.hasNext()) {
                // 邻接表迭代器有元素，获取元素
                x = it.next();
                if (!marked[x]) {
                    // 顶点未被标记，标记计数+1
                    marked[x] = true;
                    count++;
                    if (it.hasNext()) {
                        // 邻接表迭代器有元素重新入栈
                        path.push(it);
                    }
                    // 深度优先原则，当前迭代器入栈，新标记顶点的邻接表迭代器入栈，下次循环优先访问
                    Iterable<Integer> iterable = digraph.adj(x);
                    if (iterable != null && (it = iterable.iterator()) != null){
                        path.push(it);
                    }
                    break;
                }
            }

        }
    }

    /**
     * 从起点s到顶点v是否可达
     * @param  v 顶点
     * @return {@code true} if there is a directed path, {@code false} otherwise
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public boolean marked(int v) {
        validateVertex(v);
        return marked[v];
    }

    /**
     * 返回从起点可达的所有顶点数量
     * @return 返回从起点可达的所有顶点数量
     */
    public int count() {
        return count;
    }

    /**
     * 校验顶点索引v是否在0~V-1之间
     * @param v 顶点v
     */
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
        }
    }

    /**
     * 校验顶点集合
     * @param vertices  顶点集合
     */
    private void validateVertices(Iterable<Integer> vertices) {
        if (vertices == null) {
            throw new IllegalArgumentException("argument is null");
        }
        int V = marked.length;
        int count = 0;
        for (Integer v : vertices) {
            count++;
            if (v == null) {
                throw new IllegalArgumentException("vertex is null");
            }
            validateVertex(v);
        }
        if (count == 0) {
            throw new IllegalArgumentException("zero vertices");
        }
    }
}